//#pragma once
//#include <vector>
//#include <iostream>
//
//enum State
//{
//	EMPTY,
//	EXIST,
//	DELETE
//};
//
//template <class K, class V>
//struct HashNode
//{
//	std::pair<K, V> _kv;
//	State _sta;  //状态
//};
//
////hash int
//template <class K>
//struct HashFunc
//{
//	size_t operator()(const K& key)
//	{
//		return (size_t)key;
//	}
//};
//
////字符串模板特化,string
//template <>
//struct HashFunc<std::string>
//{
//	size_t operator()(const std::string& key)
//	{
//		//BKDR方法
//		size_t hash = 0;
//		for (auto ch : key)
//		{
//			hash = hash * 31 + ch;
//		}
//
//		return hash;
//	}
//};
//
//template <class K, class V, class Hash = HashFunc<K>>
//class HashTable
//{
//	typedef HashNode<K, V> node;
//public:
//	HashTable()
//	{
//		_table.resize(10);
//	}
//
//	bool insert(const std::pair<K, V>& kv)
//	{
//
//		if (find(kv.first))
//		{
//			return false;
//		}
//
//		//负载因子,整数不会出小数,扩大十倍
//		if (_n * 10 / _table.size() == 7)
//		{
//			//扩容
//			size_t newsize = _table.size() * 2;
//			HashTable<K, V, Hash> newhash;
//			newhash._table.resize(newsize);
//			for (int i = 0; i < _table.size(); i++)
//			{
//				if (_table[i]._sta == EXIST)
//				newhash.insert(_table[i]._kv);
//			}
//			//交换数组
//			_table.swap(newhash._table);
//		}
//
//		//线性探测
//		Hash hf;
//		size_t hashi = hf(kv.first) % _table.size();
//		while (_table[hashi]._sta == EXIST)
//		{
//			hashi++;
//			hashi %= _table.size();
//		}
//
//		_table[hashi]._kv = kv;
//		_table[hashi]._sta = EXIST;
//		_n++;
//
//		return true;
//	}
//
//	node* find(const K& key)
//	{
//		Hash hf;
//		//线性探测,字符串需要转整数
//		size_t hashi = hf(key) % _table.size();
//		while (_table[hashi]._sta != EMPTY)
//		{
//			//删除状态不能判断为找到
//			if (_table[hashi]._sta == EXIST && _table[hashi]._kv.first == key)
//			{
//				return &_table[hashi];
//			}
//			hashi++;
//			hashi %= _table.size();
//		}
//
//		return nullptr;
//	}
//
//	//伪删除法
//	bool erase(const K& key)
//	{
//		node* del = find(key);
//		if (del != nullptr)
//		{
//			del->_sta = DELETE;
//			_n--;
//			return true;
//		}
//
//		return false;
//	}
//
//	void print()
//	{
//		for (size_t i = 0; i < _table.size(); i++)
//		{
//			if (_table[i]._sta == EXIST)
//			{
//				std::cout << "[" << i << "]->" << _table[i]._kv.first <<
//					":" << _table[i]._kv.second << std::endl;
//			}
//			else if (_table[i]._sta == EMPTY)
//			{
//				printf("[%d]->\n", i);
//			}
//			else
//			{
//				printf("[%d]->D\n", i);
//			}
//		}
//	}
//
//private:
//	std::vector<node> _table;
//	size_t _n = 0;  //个数
//};